- The general Selection Problem is to find the order statistic for any value of
- We can still get a asymptotic runtime of )!
Randomized-Select
- A divide and conquer algorithm modeled after quicksort.
- Unlike quicksort that works on both sides of the partition. Randomized-Select works on only one side of the partition.
- That is why Randomized-Select is assuming the elements are distinct.
- That is the expected runtime but the worst case runtime is
- It uses the procedure Randomized-Partition
- Randomized algorithms are called “Randomized” because a part of the algorithm relies on the output of a random-number generator.
Randomized-Select - returns the smallest element of the array , where
Pseudocode:
Python Code:
def Randomized_Select(A,p,r,i):
# Is the sub-array size 1?
if p == r:
return A[p]
# Finding our new pivot (A[q]) with randomized partition
q = Randomized_Partition(A,p,r)
k = q - p + 1 # Computes the number of elemets in the subarray A[p:q]
# That's the same as the number of elements in the low side of the partition
if i == k: # Is A[q] the ith smallest element?
return A[q]
# If not then which subarray does the ith smallest element lie?
elif i < k:
return Randomized_Select(A,p,q-1,i)
else:
return Randomized_Select(A,q+1, r, i-k)Visual from Intro to algorithms book:
